import random

from utils.tree_node import BSTreeNode
from utils.generator import Generator
from algo.tree.tree_serialize import TreeSerialize
from utils.log import Log
from utils.qs import QS


class BinaryTreeGenerator(Log):
    def __init__(self, max_nodes=20):
        super(BinaryTreeGenerator, self).__init__()
        self.max_nodes = max_nodes

    def insert(self, root, node):
        if node < root:
            if root.left is None:
                root.left = node
            else:
                self.insert(root.left, node)
        if node > root:
            if root.right is None:
                root.right = node
            else:
                self.insert(root.right, node)

    def do(self):
        g = Generator()
        root = BSTreeNode(g.single_val())
        for _ in range(self.max_nodes):
            n = BSTreeNode(g.single_val())
            self.insert(root, n)
        return root


class BinaryTreeLCA(Log):
    def __init__(self):
        # ref https://www.bilibili.com/video/BV1194y16727/?spm_id_from=333.999.0.0&vd_source=ad559e41b561d48861f70d0187e51e02
        # 00:15:26
        super(BinaryTreeLCA, self).__init__()

    def lca(self, root, node1, node2):
        if ((root is None) or (node1 is None) or (node2 is None) or
                (root == node1) or (root == node2) or (node1 < root < node2)):
            return root
        if root > node2:
            return self.lca(root.left, node1, node2)
        if root < node1:
            return self.lca(root.right, node1, node2)


if __name__ == '__main__':
    q = QS()
    random_list = []
    t = BinaryTreeGenerator().do()
    q.push(t)
    while len(q):
        n = q.pop()
        random_list.append(n)
        if n.left:
            q.push(n.left)
        if n.right:
            q.push(n.right)
    node1 = random.choice(random_list)
    node2 = random.choice(random_list)
    if node1 > node2:
        node1, node2 = node2, node1
    print(f"select {node1} and {node2} to get lca")
    print(TreeSerialize.serialize(t))

    print('lca is', BinaryTreeLCA().lca(t, node1, node2))

    # bt = BinaryTreeGenerator()
    # s1 = TreeSerialize.serialize(bt.do())
    # print(s1)
    # s2 = TreeSerialize.serialize(TreeSerialize.deserialize(s1))
    # print(s2)
